#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>

typedef struct Node {
	int val;
	Node *next, *prev;
} Node;

typedef struct List {
	Node *HEAD,
	     *end;
} List;


inline void*
my_malloc(size_t size)
{
	void *p;
	p = malloc(size);
	if (!p)
		fprintf(stderr,
			"Failed to allocate %lu bytes. Expect trouble.\n",
			size);
	return p;
}

/*
 * Returns pointer to list containing 1 useless node.
 */
List*
List_init(void)
{
	List *l;
	Node *n;

	l = (List*) my_malloc(sizeof(List));
	n = (Node*) my_malloc(sizeof(Node));
	n->prev = n->next = n;
	n->val  = 1337;
	l->HEAD = l->end = n;
	return l;
}

/*
 * Returns ptr to next node.
 */
Node*
List_remove_node(List *lst, Node *cur)
{
	Node *ret;

	if (cur == lst->end) {
		lst->end  = cur->prev;
		lst->end->next  = lst->end;
		ret = lst->end;
	} else if (cur == lst->HEAD) {
		lst->HEAD = cur->next;
		lst->HEAD->prev = lst->HEAD;
		ret = lst->HEAD;
	} else {
		cur->prev->next = cur->next;
		cur->next->prev = cur->prev;
		ret = cur->next; /**/
	}
	free(cur);

	return (ret);
}

/*
 * Insert a node before 'cur'.
 */
void
List_ins_befor(List *lst, Node *cur, int val)
{
	Node *in;

	in = (Node*) my_malloc(sizeof(Node));
	in->val = val;
	/* 'in' is a dangling node now */

	if (cur == lst->HEAD && lst->HEAD != lst->end)
		cur->prev = in;

	/* First, we doubly-link 'in' with 'cur'
	 * and 'cur->prev'. */
	in->prev = cur->prev;
	in->next = cur;

	/* Then we fix dlinking of 'ins->prev'
	 * 'ins->next' */
	if (cur == lst->HEAD) /* workaround */
		in->prev = in;
	else
		in->prev->next = in;
	cur->prev = in;

	if (cur == lst->end) {
		cur->next = cur;
	}
	if (cur == lst->HEAD) {
		in->prev = in;
		lst->HEAD = in;
	}
}

void
List_free(List *L)
{
	Node *p = L->end, /* this pointer travels around the list */
	     *f = L->end; /* this pointer is being freed */

	L->HEAD->prev = NULL;
	while (p != NULL && f != NULL) {
		p = p->prev;
		free(f);
		f = p;
	}
	free(L);
}


int
main(void)
{
	List *lst;
	Node *ptr;
	int val;
	char cmd[128];

	lst = List_init();
	ptr = lst->end;
	while (scanf("%s", cmd) == 1) {
		if (!strcmp(cmd, "Begin"))
			ptr = lst->HEAD;
		else if (!strcmp(cmd, "End"))
			ptr = lst->end;
		else if (!strcmp(cmd, "Next"))
			ptr = ptr->next;
		else if (!strcmp(cmd, "Prev"))
			ptr = ptr->prev;
		else if (!strcmp(cmd, "Delete"))
			ptr = List_remove_node(lst, ptr);
		else if (!strcmp(cmd, "Insert")) {
			(void) scanf("%d", &val);
			List_ins_befor(lst, ptr, val);
		} else if (!strcmp(cmd, "Print"))
			(void) printf("%d\n", ptr->val);
		else
			(void) fprintf(stderr,
					"Unknown command \"%s\"\n", cmd);
	}
	List_free(lst);
	return (0);
}
